class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        left = matrix[0][0]
        right = matrix[-1][-1]
        m = len(matrix)
        n = len(matrix[0])

        def search(i, value):
            l = 0
            r = n - 1
            while l < r:
                mid = (l + r) // 2
                if matrix[i][mid] <= value:
                    l = mid + 1
                else:
                    r = mid
            if matrix[i][l] <= value:
                return l + 1
            else:
                return l

        def cal(value):
            total = 0
            for i in range(m):
                total += search(i, value)
            return total

        while left < right:
            mid = (left + right) // 2
            num = cal(mid)
            if num >= k:
                right = mid
            else:
                left = mid + 1
        return right



data = Solution()
matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]]
k = 7
print(data.kthSmallest(matrix, k))
